package com.lw.leetcode.str.b;

/**
 * Created with IntelliJ IDEA.
 * 1850. 邻位交换的最小次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/5 21:42
 */
public class GetMinSwaps {

    public static void main(String[] args) {
        GetMinSwaps test = new GetMinSwaps();

        // 2
//        String str = "5489355142";
//        int n = 4;

        // 4
//        String str = "11112";
//        int n = 4;

        // 1
//        String str = "00123";
//        int n = 1;

        // 1
        String str = getStr();
        int n = 20;

        int minSwaps = test.getMinSwaps(str, n);
        System.out.println(minSwaps);
    }

    private int length;

    public int getMinSwaps(String num, int k) {
        char[] chars = num.toCharArray();
        char[] items = num.toCharArray();
        this.length = num.length();
        for (int i = 0; i < k; i++) {
            find(chars);
        }
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (items[i] == chars[i]) {
                continue;
            }
            int st = i + 1;
            char c = items[i];
            for (int j = i + 1; j < length; j++) {
                if (c == chars[j]) {
                    st = j;
                    break;
                }
            }
            count += st - i;
            while (st > i) {
                chars[st] = chars[st - 1];
                st--;
            }
        }
        return count;
    }

    private void find(char[] arr) {
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i] > arr[i - 1]) {
                int l = length - 1;
                char t = arr[i - 1];
                for (int j = i + 1; j < length; j++) {
                    if (arr[j] <= t) {
                        l = j - 1;
                        break;
                    }
                }
                arr[i - 1] = arr[l];
                arr[l] = t;
                int m = i + ((length - 1 - i) >> 1);
                int end = i + length - 1;
                while (i <= m) {
                    t = arr[i];
                    arr[i] = arr[end - i];
                    arr[end - i] = t;
                    i++;
                }
                return;
            }
        }
    }

    private static String getStr() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 1000; i++) {
            int a = (int) (Math.random() * 10);
            sb.append((char) (a + '0'));
        }
        System.out.println(sb);
        return sb.toString();
    }

}
